package master;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author chenyw
 * @date 2022/9/24 10:43
 * 为运算表达式设计优先级
 */
public class M241diffWaysToCompute {
    Map<String, List<Integer>> map = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> res = dfs(expression);
        return res;
    }

    private List<Integer> dfs(String str) {
        //递归出口，如果当前叶子结点是数字（没有运算符）
        if (isDigit(str) > 0) {
            return new ArrayList<Integer>(){{add(Integer.valueOf(str));}};
        }
        //使用map就已经计算过的子串
        if (map.containsKey(str)) {
            return map.get(str);
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                List<Integer> left = dfs(str.substring(0, i));
                List<Integer> right = dfs(str.substring(i + 1));
                int val = 0;
                //遍历left 和 right；组合所有可能的结果
                for (Integer l : left) {
                    for (Integer r : right) {
                        switch (ch) {
                            case '+':
                                val = l + r;
                                break;
                            case '-':
                                val = l - r;
                                break;
                            case '*':
                                val = l * r;
                                break;
                            default:
                        }
                        list.add(val);
                    }
                }
            }
        }
        map.put(str, list);
        return list;
    }

    private int isDigit(String str) {
        for (int i = 0; i < str.length(); i++) {
            if (!Character.isDigit(str.charAt(i))) {
                return -1;
            }
        }
        return 1;
    }
}
